1. Field of the Invention
The present invention relates generally to improvements in information storage, retrieval and processing. More particularly, the present invention relates to improvements in content-addressable memory (CAM) used to process data packets or other information in a digital telecommunication system.
2. Description of Prior Art
A content-addressable memory (CAM) is a digital electronic memory circuit capable of storing quantities of digital data which can be simultaneously addressed or searched in response to an input data word. A CAM typically includes an array of memory cells, each memory cell storing a single data bit. The array of cells is usually organized into a number of rows and columns, with each row representing a group of stored data bits, or data words, and each column including individual stored data bits at a particular position in each data word. A CAM may output the actual data values stored in its memory cells when addressed by an input word. In its memory cell organization and data storage aspects, a CAM is thus similar to a random access memory (RAM). However, unlike a RAM, the CAM may also output a match signal indicating whether or not a given input word matches any of the data words stored in the entire CAM cell array. The CAM can thus provide parallel searching of the stored data words in each row of the array. This parallel searching function facilitates data storage and retrieval in a variety of different applications.
One important application of CAM is data packet processing in a broadband integrated services digital network (BISDN) operating in asynchronous transfer mode (ATM). BISDN is presently being developed to provide a high-capacity wide-area digital network suitable for multimedia communication. The variable high-speed data requirements of BISDN are efficiently handled using flexible packet processing techniques such as those provided by an ATM communication system. Such a system dynamically allocates data packet time slots to various users to obtain maximum network capacity for variable data traffic, rather than assigning fixed time slots to accommodate peak user data traffic as in synchronous transfer mode (STM) communication. The dynamic allocation of available bandwidth is accomplished, in part, by including a header in each data packet which identifies the packet by content rather than by a fixed time slot. The information in the header is checked against a look-up table to determine the appropriate processing steps for its corresponding packet. Portions of the look-up table may be implemented as a CAM to facilitate retrieval of stored packet processing information.
A significant problem with existing CAM systems is the effect of data fields which are not needed in a particular processing operation, commonly referred to as "don't care" data. In general, the don't care data stored in a CAM will slow down the process of matching an input word with the stored data words. In one currently used approach, the CAM includes a capability for masking particular columns of data bits within the CAM by setting a CAM mask register. However, this approach often uses an external pre-processing RAM to determine, for example, if a particular input packet header to be processed includes don't care values, as well as the bit positions of the don't care values. Additional hardware and processing steps are therefore usually required to provide such a data bit masking function within the CAM.
Another currently used technique for handling don't care data within a CAM is multi-step searching of the data words stored in the CAM. For example, if one or more fields of data bits may contain don't care values in a given application, the CAM may first be searched with one field of data bits masked off using a data bit masking capability and a CAM mask register, and then if no match is found, additional searches may be performed with other possible don't care fields masked off. Although this approach avoids the use of an additional external pre-processing RAM to determine which field of bits should be masked, the number of CAM searches which must be performed to check for matches for a given CAM input word is increased by a factor of 2.sup.j -1 for matching an input word divided into j fields, each of which may or may not contain don't care values.
An alternative to masking of don't care data fields in a CAM is to actually encode and store don't care bits as such. This approach is known as ternary encoding, and involves encoding three possible data states, logic 1, logic 0, and don't care, within the stored data words. Two data bits are therefore required to store each of these three data states. See S. Ramirez-Chavez, "Encoding Don't Cares in Static and Dynamic Content-Addressable Memories" IEEE Transactions on Circuits and Systems, Vol. 39, No. 8, August 1992. Although this storage technique may result in a decrease in the number of memory cells required to store, for example, intervals of sequential integers, ternary encoding will approximately double the required memory storage capacity in many conventional CAM applications. The larger required memory size results in increased system cost, increased vulnerability to failure, and larger processing overhead. Ternary encoding is therefore generally not considered a suitable technique for implementing telecommunication systems such as BISDN.
As is apparent from the above, a need exists for an improved CAM which is capable of efficiently masking fields of don't care data bits without using a pre-processing RAM, without additional searching steps or without unduly increasing the required CAM memory capacity.